﻿using Newtonsoft.Json;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace DiscreteMath
{
    /// <summary>
    /// Represents a nondeterministic automaton - a recognition device for regular languages. Abbreviated as NFA.
    /// An NFA may transit from a single state to a set of states using a single letter (including the empty word).
    /// </summary>
	public class NondeterministicAutomaton : FiniteStateMachine, ILanguageOperator<NondeterministicAutomaton>
    {
        [JsonProperty("transitions")]
        public TransitionDictionary Transitions { get; set; }

        #region Contructors
		
		[JsonConstructor]
        /// <summary>
        /// Initializes a new <see cref="NondeterministicAutomaton"/> with the specified states, 
        /// alphabet, transitions, starting state and final states.
        /// </summary>
        /// <param name="states">The set of states of the automaton.</param>
        /// <param name="alphabet">The set of letter the automaton's alphabet consists of.</param>
        /// <param name="transitions">The transitions that the automaton will follow when reading a word.</param>
        /// <param name="starting">The state that automaton will start in.</param>
        /// <param name="final">The set of states that the automaton considers final.</param>
        public NondeterministicAutomaton(
			ISet<State> states, 
			ISet<char> alphabet,
			TransitionDictionary transitions, 
			State startState, 
			ISet<State> finalStates) :
			base(states, alphabet, startState, finalStates)
		{
			if (transitions == null)
				throw new ArgumentNullException("transitions");

			this.Transitions = transitions;
		}

        /// <summary>
        /// Initializes a new <see cref="NondeterministicAutomaton"/> with the specified states, 
        /// alphabet, transitions, startingState state and finalStates states.
        /// </summary>
        /// <param name="states">The set of states of the automaton.</param>
        /// <param name="alphabet">The set of letter the automaton's alphabet consists of.</param>
		/// <param name="transitions">A <c>deterministic</c> function to compute the automaton's transition table.</param>
        /// <param name="startingState">The state that automaton will start in.</param>
        /// <param name="finalStates">The set of states that the automaton considers finalStates.</param>
		public NondeterministicAutomaton(
			ISet<State> states,
			ISet<char> alphabet,
			Func<State, char, ISet<State>> transitions,
			State startingState,
			ISet<State> finalStates) :
			base(states, alphabet, startingState, finalStates)
		{
			if (transitions == null)
				throw new ArgumentNullException("transitions");

			this.Transitions = new TransitionDictionary();
			foreach (var letter in alphabet.Union(SpecialSigns.EmptyWord))
			{
				foreach (var state in states)
				{
					this.Transitions.Add(new Configuration(state, letter), transitions(state, letter));
				}
			}
		}

        protected NondeterministicAutomaton(
            ISet<State> states,
            ISet<char> alphabet,
            State startingState,
            ISet<State> finalStates) :
            base(states, alphabet, startingState, finalStates)
        { 
        }

        #endregion

        #region Operations

        /// <summary>
        /// Produces a <see cref="NondeterministicAutomaton" /> that recognizes the set union of the
        /// languages accepted by this automaton and the given one.
        /// </summary>
        /// <param name="automaton">A <see cref="NondeterminiticAutomaton" />
        /// whose language to unite with the current one.</param>
        /// <returns>
        /// A <see cref="NondeterministicAutomaton" /> that accepts the set union of the
        /// languages accepted by this automaton and the specified one.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">automaton</exception>
        /// <exception cref="System.InvalidOperationException">Both automata must work on the same alphabet</exception>
        public NondeterministicAutomaton Union(NondeterministicAutomaton automaton)
		{
            if (automaton == null)
                throw new ArgumentNullException("automaton");

            // Rename conflicts between the states of the automata
            State renamedStarting;
            ISet<State> renamedStates, renamedFinal;
            TransitionDictionary renamedTransitions;

            Algorithms.RenameDuplicates(this, automaton, (state) => state + "'", out renamedStates, out renamedStarting, out renamedFinal, out renamedTransitions);

			State starting = new State(Guid.NewGuid().ToString());
			ISet<char> alphabet = this.Alphabet.Union(automaton.Alphabet).ToSet();
			ISet<State> states = this.States.Union(renamedStates).Union(starting).ToSet();
			ISet<State> final = this.Final.Union(renamedFinal).ToSet();
			if (this.IsStartStateFinal || automaton.IsStartStateFinal)
			{
				final.Add(starting);
			}
			var transitions = this.Transitions.Union(renamedTransitions).ToTransitionDictionary();
			foreach (var letter in alphabet)
			{
				var childStates = new HashSet<State>();
				var configuration1 = new Configuration(this.StartState, letter);
				var configuration2 = new Configuration(renamedStarting, letter);
				childStates.UnionWith(this.Transitions[configuration1]);
				childStates.UnionWith(renamedTransitions[configuration2]);

				transitions.Add(new Configuration(starting, letter), childStates);
			}

			var union = new NondeterministicAutomaton(states, alphabet, transitions, starting, final);
            return union;
		}

        /// <summary>
        /// Produces a <see cref="NondeterministicAutomaton"/> that recognizes the concatenation of the languages of this
        /// automaton and the specified one.
        /// </summary>
        /// <param name="automaton">A <see cref="NondeterministicAutomaton"/> whose language to concatenate to the current one.</param>
        /// <returns>A <see cref="NondeterministicAutomaton"/> that accept the language produced by concatenating the
        /// language accepted by the current automaton and the specified automaton.</returns>
		public NondeterministicAutomaton Concatenate(NondeterministicAutomaton automaton)
		{
            if (automaton == null)
                throw new ArgumentNullException("automaton");

            // Rename conflicts between the states of the automata
            State renamedStarting;
            ISet<State> renamedStates, renamedFinal;
            TransitionDictionary renamedTransitions;
            Func<string, string> renamingFunction = (state) => state + "'";

            Algorithms.RenameDuplicates(this, automaton, renamingFunction, out renamedStates, out renamedStarting, out renamedFinal, out renamedTransitions);

            var states = this.States.Union(renamedStates).ToSet();
            var final = renamedFinal.ToSet();
            var transitions = this.Transitions.Union(renamedTransitions).ToTransitionDictionary();
            var alphabet = this.Alphabet.Union(automaton.Alphabet).ToSet();

			var starting = this.StartState;
			if (automaton.IsStartStateFinal)
			{
				final.UnionWith(this.Final);
			}
			foreach (var letter in automaton.Alphabet)
			{
				var configuration = new Configuration(renamedStarting, letter);
				ISet<State> children;
				if (renamedTransitions.TryGetValue(configuration, out children))
				{
					foreach (var finalState in this.Final)
					{
						var currentConfiguration = new Configuration(finalState, letter);
						transitions.Add(currentConfiguration, children);
					}
				}
			}

			var concatenated = new NondeterministicAutomaton(states, alphabet, transitions, starting, final);
            return concatenated;
		}
		
        /// <summary>
        /// Produces a <see cref="NondeterministicAutomaton"/> that recognizes the Klenee star of the language accepted by
        /// the current automaton.
        /// </summary>
        /// <returns>A <see cref="NondeterministicAutomaton"/> that accepts the language produces by Klenee star over
        /// the language accepted by the current automaton.</returns>
		public NondeterministicAutomaton KleneeStar()
		{
			var starting = new State(Guid.NewGuid().ToString());
			var states = new HashSet<State>(this.States.Union(starting));
            var final = new HashSet<State>(this.Final.Union(starting));
			var transitions = new TransitionDictionary(this.Transitions);
			foreach (var letter in this.Alphabet.Union(SpecialSigns.EmptyWord))
			{
				var configuration = new Configuration(this.StartState, letter);
                if (this.Transitions.ContainsKey(configuration))
                {
                    ISet<State> possibleStates = this.Transitions[configuration];
                    Debug.WriteLine("Letter: {0}, States: {1}", letter, possibleStates.Print());
                    foreach (var child in final)
                    {
                        var currentConfiguration = new Configuration(child, letter);
                        transitions.Add(currentConfiguration, possibleStates);
                    }
                }
			}			
			var klenee = new NondeterministicAutomaton(states, this.Alphabet, transitions, starting, final);
            return klenee;
		}

        /// <summary>
        /// Produces a <see cref="DeterministicAutomaton"/> that recognizes the same language as the current 
        /// <see cref="NondeterministicAutomaton"/>.
        /// </summary>
        /// <returns>A <see cref="DeterministicAutomaton"/> equivalent to the current <see cref="NondeterministicAutomaton"/></returns>
		public DeterministicAutomaton Determine()
		{
            var currentTransitions = new HashSet<State> { this.StartState };
            var starting = new State(currentTransitions);
			var transitions = new TransitionDictionary();
			var states = new HashSet<State>() { starting };
			Algorithms.AddDeterministicStates(this, currentTransitions, starting, transitions, states);
			var final = new HashSet<State>(states.Where(state => 
			{
                return state.Name.ContainsAny(this.Final);
			}));

			return new DeterministicAutomaton(states, this.Alphabet, transitions, starting, final);
		}

        /// <summary>
        /// Produces a <see cref="DeterministicAutomaton"/> that accepts the same language as the given 
        /// regular expression generates.
        /// </summary>
        /// <param name="regex">The regular expression to construct the machine from.</param>
        /// <returns>A <see cref="DeterministicAutomaton"/> accepting the language generated by the specified regex.</returns>
        /// <exception cref="System.ArgumentException">string is null or empty;regex</exception>
        public static DeterministicAutomaton FromRegex(string regex)
        {
            if (string.IsNullOrEmpty(regex))
                throw new ArgumentException("string is null or empty", "regex");

            NondeterministicAutomaton automaton = 
                RpnConverter<NondeterministicAutomaton>.EvaluateRegex(regex, Algorithms.CreateLetterReadingAutomaton);

            return automaton.Determine().Minimize();
        }

        /// <summary>
        /// Returns a regular expression that generates the same language as this automaton accepts.
        /// </summary>
        /// <returns>A regular expression whose language is equivalent to the language of the current machine.</returns>
        public string ToRegex()
        {
            // Construct a special automaton - one that has a single final state, no transitions go into the start state
            // and no transitions go out of the final state.
            State starting = "STARTING",
                final = "FINAL";
            var special = this.ConstructSpecial(starting, final);
            var tempExpressions = new Dictionary<Tuple<State, State>, string>();
            foreach (var transition in special.Transitions)
            {
                foreach (var state in transition.Value)
                {
                    var key = Tuple.Create(transition.Key.State, state);
                    if (tempExpressions.ContainsKey(key))
                    {
                        tempExpressions[key] += SpecialSigns.UnionSign + transition.Key.Letter.ToString();
                    }
                    else
                    {
                        tempExpressions[key] = transition.Key.Letter.ToString();
                    }
                }
            }

            // Remove all states but the new start and final. Add regular expressions to the connections between the states.
            foreach (State state in this.States)
            {
                Algorithms.RemoveStateFromSpecialAutomaton(state, special, tempExpressions);             
            }

            // Take the expression between the start state and the final state and remove empty words, unions with empty words,
            // empty braces and for clarity braces that contain of a single letter.
            string finalExpression = tempExpressions[Tuple.Create(starting, final)]
                .Replace(SpecialSigns.EmptyWord.ToString(), string.Empty)
                .Replace(SpecialSigns.UnionSign + ")", ")")
                .Replace("()", string.Empty);
            
            finalExpression = Regex.Replace(finalExpression, @"\(\S\)", (match) => match.Value.Substring(1, 1));

            return finalExpression;
        }

        private NondeterministicAutomaton ConstructSpecial(State starting, State final)
        {
            var finalStates = new HashSet<State>() { final };
            var states = new HashSet<State>(this.States.Union(starting, final));
            var transitions = new TransitionDictionary(this.Transitions);
            transitions.Add(starting, SpecialSigns.EmptyWord, new HashSet<State>() { this.StartState });
            foreach (State state in this.Final)
            {
                transitions.Add(state, SpecialSigns.EmptyWord, finalStates);
            }

            var special = new NondeterministicAutomaton(states, this.Alphabet, transitions, starting, finalStates);
            return special;
        }

		public static NondeterministicAutomaton operator ~(NondeterministicAutomaton automaton)
		{
            if (automaton == null)
                throw new ArgumentNullException("automaton");

            return automaton.KleneeStar();
		}

        public static NondeterministicAutomaton operator +(
			NondeterministicAutomaton automaton1, 
			NondeterministicAutomaton automaton2)
		{
            if (automaton1 == null)
                throw new ArgumentNullException("automaton1");

			return automaton1.Union(automaton2);
		}

		public static NondeterministicAutomaton operator *(
			NondeterministicAutomaton automaton1,
			NondeterministicAutomaton automaton2)
		{
            if (automaton1 == null)
                throw new ArgumentNullException("automaton1");

			return automaton1.Concatenate(automaton2);
		}
        
        #endregion

        /// <summary>
        /// Reads the given word and returns a value indicating whether the machine accepts it.
        /// </summary>
        /// <param name="word">The word to read.</param>
        /// <returns>
        ///   <c>True</c> if the machine accepts the word, <c>False</c> otherwise.
        /// </returns>
        public override bool ReadWord(IEnumerable<char> word)
		{
            return this.ReadWord(word, false);
		}

        /// <summary>
        /// Reads the given word and returns a value indicating whether the machine accepts it and may also print
        /// the states that the automaton goes trough.
        /// </summary>
        /// <param name="word">The word to read.</param>
        /// <param name="debuggingEnabled">If set to <c>true</c> this method will print the states the automaton
        /// goes trough in the Output window.</param>
        /// <returns>
        ///   <c>True</c> if the machine accepts the word, <c>False</c> otherwise.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">word</exception>
        public bool ReadWord(IEnumerable<char> word, bool debuggingEnabled)
        {
            if (word == null)
                throw new ArgumentNullException("word");

			if (!this.Alphabet.IsSupersetOf(word))
				throw new ArgumentException("Some of the letters in the word are not present in the automaton's alphabet.", "word");

            if (word.Equals(SpecialSigns.EmptyWord.ToString()))
                return this.IsStartStateFinal;

            var currentSubset = new HashSet<State>() { this.StartState };
            var nextSubset = new HashSet<State>();
            foreach (var letter in word)
            {
                foreach (var state in currentSubset)
                {
                    var currentConfiguration = new Configuration(state, letter);
                    var epsilonConfiguration = new Configuration(state, SpecialSigns.EmptyWord);
                    nextSubset.UnionWith(this.Transitions[currentConfiguration]);
                    nextSubset.UnionWith(this.Transitions[epsilonConfiguration]);
                }
                currentSubset = nextSubset;
                nextSubset = new HashSet<State>();
            }
            currentSubset.IntersectWith(this.Final);
            var recognizesWord = currentSubset.Count != 0;
            return recognizesWord;
        }

        /// <summary>
        /// Produces a string that prints information about the current <see cref="NondeterministicAutomaton"/>
        /// in a human-readable way. Useful for debugging.
        /// </summary>
        /// <returns>A string representing the <see cref="NondeterministicAutomaton"/></returns>
		public string Print()
		{
			var builder = new StringBuilder();
            builder.AppendLine("Starting: " + this.StartState);

			builder.AppendLine("States: ");
			foreach (var state in this.States)
			{
				builder.AppendLine(state.Name);
			}
			builder.AppendLine("Transitions: ");
			builder.Append(this.PrintTransitions(Environment.NewLine));
			builder.AppendLine("Final: ");
			foreach (var item in this.Final)
			{
				builder.AppendLine(item.Name);
			}
			return builder.ToString();
		}

		private string PrintTransitions(string delimiter)
		{
			StringBuilder text = new StringBuilder();
			bool shouldAppendDelimiter = !string.IsNullOrEmpty(delimiter);
			foreach (var transition in this.Transitions)
			{
				text.AppendFormat("({0}, {1}){2}", transition.Key.State, transition.Key.Letter, transition.Value.Print());
				if (shouldAppendDelimiter)
				{
					text.Append(delimiter);
				}
			}
			return text.ToString();
		}

        public void FilePrettyPrint()
        {
            string content = this.Print();
            char replacement = 'A';
            foreach (var state in this.States)
            {
                content = content.Replace(state, replacement.ToString());
                replacement++;
            }

            File.WriteAllText("Automaton.txt", content);
        }

        /// <summary>
        /// Container for a few algorithms so that we don't pollute the above namespace
        /// </summary>
        protected static class Algorithms
        {
            public static NondeterministicAutomaton CreateLetterReadingAutomaton(char letter, ISet<char> alphabet)
            {
                State first = Guid.NewGuid().ToString();
                State second = Guid.NewGuid().ToString();

                var states = new HashSet<State>() { first, second };
                var final = new HashSet<State>() { second };
                var starting = first;
                var transitions = new TransitionDictionary()
            {
                { first, letter, new HashSet<State>() { second } },
            };

                var automaton = new NondeterministicAutomaton(states, alphabet, transitions, starting, final);
                return automaton;
            }

            public static void AddDeterministicStates(
                NondeterministicAutomaton automaton,
                ISet<State> currentTransitions,
                State nextDeterministic, 
                TransitionDictionary transitions, 
                ISet<State> states)
		    {
                foreach (char letter in automaton.Alphabet)
                {
                    var nextTransitions = new HashSet<State>();
                    foreach (State state in currentTransitions)
                    {
                        nextTransitions.UnionWith(automaton.Transitions[state, letter]);
                    }
                    var nextState = new State(nextTransitions);
                    transitions.Add(nextDeterministic, letter, new HashSet<State>() { nextState });
                    if (!states.Contains(nextState))
                    {
                        states.Add(nextState);
                        AddDeterministicStates(automaton, nextTransitions, nextState, transitions, states);
                    }
                }
		    }

            public static void RemoveStateFromSpecialAutomaton(
                State state,
                NondeterministicAutomaton special,
                Dictionary<Tuple<State, State>, string> tempExpressions)
            {
                // Find all transitions in the given state and out of it.
                State[] transitionsIn =
                    (from transition in special.Transitions
                     where transition.Value.Contains(state) && transition.Key.State != state
                     select transition.Key.State).ToArray();

                State[] transitionsOutOf =
                    (from transition in special.Transitions
                     where transition.Key.State == state
                     select transition.Value into values
                     from ancestor in values
                     where ancestor != state
                     select ancestor).ToArray();

                string regexForLoops = string.Empty;
                if (tempExpressions.ContainsKey(Tuple.Create(state, state)))
                {
                    regexForLoops = "(" + tempExpressions[Tuple.Create(state, state)] + ")*";
                }

                // Foreach tuple of (transition in the state, transition out of state), remove the existing transitions and add the expression between them to the our dictionary
                foreach (State incomingTransition in transitionsIn)
                {
                    foreach (State outgoingTransition in transitionsOutOf)
                    {
                        var key = Tuple.Create(incomingTransition, outgoingTransition);
                        string currentRegex = tempExpressions.ContainsKey(key) ? tempExpressions[key] +
                            SpecialSigns.UnionSign : string.Empty;
                        currentRegex +=
                            "(" + tempExpressions[Tuple.Create(incomingTransition, state)] + ")" +
                            regexForLoops +
                            "(" + tempExpressions[Tuple.Create(state, outgoingTransition)] + ")";
                        tempExpressions[key] = currentRegex;
                        special.Transitions.Add(
                            incomingTransition,
                            SpecialSigns.EmptyWord,
                            new HashSet<State>() { outgoingTransition });
                    }
                }

                // Remove the state and every transition that involves it
                special.States.Remove(state);
                special.Final.Remove(state);
                
                Configuration[] transitionsToRemove = special.Transitions.Keys.Where(x => x.State == state).ToArray();
                Configuration[] transitionsToRemoveStateFrom = special.Transitions.Where(x => x.Value.Contains(state)).Select(x => x.Key).ToArray();
                foreach (Configuration key in transitionsToRemove)
                {
                    special.Transitions.Remove(key);
                }
                foreach (Configuration key in transitionsToRemoveStateFrom)
                {
                    special.Transitions[key].Remove(state);
                }
            }

            public static void
                RenameDuplicates(
                NondeterministicAutomaton comparer, 
                NondeterministicAutomaton toBeRenamed,
                Func<string, string> renamingFunction,
                out ISet<State> renamedStates,
                out State renamedStarting,
                out ISet<State> renamedFinals,
                out TransitionDictionary renamedTransitions)
            {
                // No need to rename if the states dont overlap
                if (!comparer.States.Overlaps(toBeRenamed.States))
                {
                    renamedStates = toBeRenamed.States;
                    renamedStarting = toBeRenamed.StartState;
                    renamedFinals = toBeRenamed.Final;
                    renamedTransitions = toBeRenamed.Transitions;

                    return;
                }
                // Calculate the intersection of the states and the difference between them. Use the renaming function to generate rules. Note: the renaming function
                // need not be deterministic, so calculate it only once.
                IEnumerable<State> intersection = comparer.States.Intersect(toBeRenamed.States);
                IEnumerable<State> union = comparer.States.Union(toBeRenamed.States);
                IEnumerable<State> difference = toBeRenamed.States.Except(intersection);
                IEnumerable<State> differenceFinal = difference.Where(x => toBeRenamed.Final.Contains(x));
                Dictionary<State, State> renamingRules = intersection.ToDictionary(state => state, state => new State(renamingFunction(state)));

                // Make sure that after renaming no conflicts occur
                while (comparer.States.Overlaps(renamingRules.Values) || toBeRenamed.States.Overlaps(renamingRules.Values))
                {
                    intersection = union.Intersect(renamingRules.Values);
                    foreach (var state in intersection)
                    {
                        renamingRules[state] = renamingFunction(state);
                    }
                }

                // Calculate states, starting, final states
                renamedStates = renamingRules.Values.ToSet();
                renamedStates.UnionWith(difference);
                renamedStarting = renamingRules.ContainsKey(toBeRenamed.StartState) ? renamingRules[toBeRenamed.StartState] : toBeRenamed.StartState;
                renamedFinals =
                    (from pairOfStates in renamingRules
                     where toBeRenamed.Final.Contains(pairOfStates.Key)
                     select pairOfStates.Value).Union(differenceFinal).ToSet();

                renamedTransitions = RenameTransitions(toBeRenamed, renamingRules);
            }

            private static TransitionDictionary RenameTransitions(NondeterministicAutomaton toBeRenamed, Dictionary<State, State> renamingRules)
            {
                // When renaming transitions - 
                // 1. remove configurations whose states are renamed 
                // 2. replace the latter with configurations whose states are the renamed equivalents
                // 3. replace states with their renamed equivalents in the right hand side of the rules.
                var renamedTransitions = new TransitionDictionary(toBeRenamed.Transitions);
                var outgoingTransitions = renamedTransitions.Where(x => renamingRules.ContainsKey(x.Key.State)).ToArray();
                foreach (var transition in outgoingTransitions)
                {
                    renamedTransitions.Remove(transition.Key);
                    renamedTransitions.Add(renamingRules[transition.Key.State], transition.Key.Letter, transition.Value);
                }

                foreach (var transition in renamedTransitions)
                {
                    var toBeReplaced = transition.Value.Where(x => renamingRules.ContainsKey(x)).ToArray();
                    foreach (var state in toBeReplaced)
                    {
                        transition.Value.Remove(state);
                        transition.Value.Add(renamingRules[state]);
                    }
                }
                return renamedTransitions;
            }
        }
	}
}
